#pragma once
#include<string>
#include<iostream>
#include"bit_set.hpp"
using namespace std;

//仿函数1，用于对对值哈希映射
struct BKDRHash
{
  size_t operator()(const string& key)
    {
      size_t hash=0;
      for(auto e:key)
      {
          hash+=e;//这里还是有缺陷，如果插入的字符串“abc”和“acb”，他们转出的整形值都是一样的
          hash*=31;//这里就是为了解决这种冲突，但只是减少冲突，冲突永远存在，因为整形的值是有限的，但是字符串的可能性无穷多
      }
      return hash;
  }
};

//仿函数2，用于对对值哈希映射
struct APHash
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for (size_t i = 0; i < key.size(); i++)
        {
            char ch = key[i];
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }
        return hash;
    }
};

//仿函数3，用于对对值哈希映射
struct DJBHash
{
    size_t operator()(const string& key)
    {
        size_t hash = 5381;
        for(auto ch : key)
        {
            hash += (hash << 5) + ch;
        }
        return hash;
    }
};


template<size_t N,class K=string,class HashFunc1=BKDRHash,class HashFunc2=APHash,class HashFunc3=DJBHash>
class BloomFilter
{
public:
    void Set(const K& key)
    {
        size_t hash1=HashFunc1()(key)%N;//HashFunc1()(key)%N是什么意思呢，这里就是用了匿名对象，以前我们是：1.HashFunc1 hf 2.hf(key)%N
        size_t hash2=HashFunc2()(key)%N;
        size_t hash3=HashFunc3()(key)%N;
        
        _bs.set(hash1);
        _bs.set(hash2);
        _bs.set(hash3);
    }
    bool Test(const K& key)
    {
        //判断是准确的
        size_t hash1=HashFunc1()(key)%N;//HashFunc1()(key)%N是什么意思呢，这里就是用了匿名对象，以前我们是：1.HashFunc1 hf 2.hf(key)%N
        if(_bs.test(hash1)==false)//判断对应的比特位在不在
            return false;
        size_t hash2=HashFunc2()(key)%N;
        if(_bs.test(hash2)==false)
            return false;
        size_t hash3=HashFunc3()(key)%N;
        if(_bs.test(hash3)==false)
            return false;
        
        //存在误判的
        return true;
    }
private:
    bit::bit_set<N> _bs;//位图
};

void TestBF1()
{
    BloomFilter<100> bf;
    bf.Set("毕财华");
    bf.Set("王雪平");
    bf.Set("孙悟空");
    bf.Set("沙悟净");
    bf.Set("猪八戒");
    bf.Set("唐僧");

    cout<<bf.Test("毕财华")<<endl;
    cout<<bf.Test("李海婷")<<endl;
    cout<<bf.Test("毕财华1")<<endl;
    cout<<bf.Test("李海婷1")<<endl;
    cout<<bf.Test("毕财华 ")<<endl;
    cout<<bf.Test("李海婷 ")<<endl;
    
}

void TestBF2()//测试布隆过滤器
{
    srand((unsigned int)time(0));
    const size_t N = 100000;
    BloomFilter<N * 10> bf;

    std::vector<std::string> v1;
    //std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
    std::string url = "猪八戒";

    for (size_t i = 0; i < N; ++i)
    {
        v1.push_back(url + std::to_string(i));
    }

    for (auto& str : v1)
    {
        bf.Set(str);
    }

    // v2跟v1是相似字符串集（前缀一样），但是不一样
    std::vector<std::string> v2;
    for (size_t i = 0; i < N; ++i)
    {
        std::string urlstr = url;
        urlstr += std::to_string(9999999 + i);
        v2.push_back(urlstr);
    }

    size_t n2 = 0;
    for (auto& str : v2)
    {
        if (bf.Test(str)) // 误判
        {
            ++n2;
        }
    }
    cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

    // 不相似字符串集
    std::vector<std::string> v3;
    for (size_t i = 0; i < N; ++i)
    {
        //string url = "zhihu.com";
        string url = "孙悟空";
        url += std::to_string(i + rand());
        v3.push_back(url);
    }

    size_t n3 = 0;
    for (auto& str : v3)
    {
        if (bf.Test(str))
        {
            ++n3;
        }
    }
    cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}
